/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年10月28日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int size = s.size();
        vector<vector<int>>dp(size, vector<int>(size, 0));
        for(int i  = size-1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i+1; j < size; j++){
                if(s[i] == s[j]){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        return dp[0][size-1];
    }
};
